package cn.initcap.algorithm.leetcode;

/**
 * 斐波那契，兔子问题
 *
 * @author initcap
 * @date Created in 2018/8/31 AM9:51.
 */
public class Fibonacci {

    private static final int INIT_MONTH = 2;
    static int[] memo;

    public static void main(String[] args) {
        int n = 40;
        long start = System.currentTimeMillis();
        System.out.println(count(n));
        long end = System.currentTimeMillis();
        // 将计算过的值进行缓存，减少计算量
        memo = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            memo[i] = -1;
        }
        long startup = System.currentTimeMillis();
        System.out.println(fib(n));
        long endup = System.currentTimeMillis();
        long startdynamic = System.currentTimeMillis();
        System.out.println(fibdynamic(n));
        long enddynamic = System.currentTimeMillis();
        System.out.println("尚未优化运行时长: " + (end - start) +
                "ms,优化后时长: " + (endup - startup) +
                "ms,动态规划: " + (enddynamic - startdynamic) + "ms");
    }

    /**
     * O(2^n) 指数级时间复杂度
     *
     * @param n 个数
     * @return 总和
     */
    private static int count(int n) {
        if (n < 1) {
            throw new IllegalArgumentException("您传入的参数不合法");
        }
        if (n == 1 || n == INIT_MONTH) {
            return 1;
        }
        return count(n - 1) + count(n - 2);
    }

    /**
     * 斐波那契算法优化,记忆化搜索 O(n) 自顶向下解决问题
     *
     * @param n 个数
     * @return 总和
     */
    private static int fib(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (memo[n] == -1) {
            memo[n] = fib(n - 1) + fib(n - 2);
        }
        return memo[n];
    }

    /**
     * 动态规划 自下而上解决问题 O(n)
     *
     * @param n 个数
     * @return 总和
     */
    private static int fibdynamic(int n) {
        int[] mem = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            mem[i] = -1;
        }

        mem[0] = 0;
        mem[1] = 1;
        for (int i = 2; i <= n; i++) {
            mem[i] = mem[i - 1] + mem[i - 2];
        }
        return mem[n];
    }

}
